
# 二分查找，也叫折半查找，前提是按照顺序的
def binarySearch(alist,item):
    first = 0
    last = len(alist) - 1
    found = False

    if len(alist) == 0:
        return False

    while last >= first and not found:
        midpoint = (last + first)//2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return found

# 二分查找本身就是分而治之的思想，因此可以采用递归的方式来解决问题
def binarySearch01(alist,item):
    if len(alist) == 0:
        return False
    else:
        midpoint = len(alist)//2
        if alist[midpoint] == item:
            return True
        else:
            if item > alist[midpoint]:
                return binarySearch01(alist[midpoint+1:],item)
            else:
                return binarySearch01(alist[:midpoint-1],item)

def binarySearch02(alist,item,first,last):
    if len(alist) == 0:
        return False
    else:
        midpoint = (first + last)//2
        if alist[midpoint] == item:
            return True
        else:
            if item > alist[midpoint]:
                return binarySearch02(alist,item,midpoint,last)
            else:
                return binarySearch02(alist,item,first,midpoint)



if __name__ == '__main__':
    testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42, ]
    print(binarySearch(testlist, 3))
    print(binarySearch01(testlist, 13))
    print(binarySearch02(testlist, 13,0,len(testlist)-1))